In a system of database shards, data items, such as records or rows or documents, can be distributed among multiple separate, independent databases, called shards. In such a system, data items typically are not, and are not permitted to be, duplicated among the shards. Thus, in such a system, a particular data item will be located on only one of the several shards at any given time. In order for a client to determine which of the several shards contains the particular data item, the client can input the data item's primary key—which uniquely identifies the particular data item—into a hash function. The hash function computes, based on the primary key, the identity of the shard on which the particular data item is currently stored. For example, a hash function might divide a numeric primary key by the quantity of shards in the system and then take the remainder (essentially a modulo operation) to be the identifier for the shard that contains the particular data item. Using such a hash function to determine, in the first place, the shard on which each data item will be stored typically causes data items to be distributed relatively evenly among the shards.
Once the client has identified the shard upon which a particular data item is located, the client can perform operations, such as read, delete, or update operations, relative to the data item. Usually, a shard system will serve numerous clients concurrently, and these clients may each perform, asynchronously to each other, operations relative to separate data items. Potentially, multiple clients could inadvertently attempt to perform operations relative to the same data item simultaneously. If this scenario were permitted to occur unhindered, then the data item could become corrupted, making the state of the shard system inconsistent. Under one approach, in order to guarantee that multiple clients will not concurrently perform operations relative to the same data item, a client that seeks to perform an operation relative to a particular data item can first be required to acquire an exclusive lock on that particular data item. Each data item can be associated with a separate lock. A client is prevented from acquiring the exclusive lock on the particular data item if another client already holds that exclusive lock; under such circumstances, the client seeking to obtain the exclusive lock must wait for the lock-holding client to release the exclusive lock. While a client is holding the exclusive lock on a particular data item, that client alone can perform operations relative to the particular data item. When the client has finished performing operations relative to the particular data item, the client can release the exclusive lock on the particular data item, thereby making the particular data item available for access by other clients.
As the quantity of data stored within the shard system grows, the capacity of the existing shards in the system might become inadequate to contain all of the data that is going to be stored in the system. It can be desirable, under those circumstances, to add one or more new shards to the system. The addition of new shards can involve the addition of new hardware computing and storage devices to contain and manage new databases. In order to attempt to balance the client access load among the shards, so that no one subset of shards becomes disproportionately burdened with client requests, the addition of new shards to the system can precipitate a redistribution of the system's stored data items among the augmented group of shards. The redistribution event, or rebalancing event, can cause data items that were formerly stored on one shard to be re-located to another shard—potentially, but not necessarily, to a newly added shard. Under one approach, rebalancing processes can obtain exclusive locks on the data items that are to be moved. After obtaining the exclusive locks on the data items, the rebalancing processes can move those data items from old shards to the new shards that have been determined by a revised hash function to be the destination for those data items. After moving the data items, the rebalancing processes can release the exclusive locks on those data items.
For as long as exclusive locks have existed, some drawbacks have attended their uses. One drawback is that while a data item's exclusive lock is held by a process, no other process can access that data item. Thus, under the lock-using rebalancing approach discussed above, clients may be largely unable to perform operations relative to the shard system while the rebalancing event proceeds; no client can obtain an exclusive lock on a data item while a rebalancing process holds that exclusive lock. Even when the rebalancing event is not ongoing, the overhead involved in clients' acquisition, maintenance, and release of locks—to guard against concurrent multiple client access—can be significant and burdensome. Even ignoring the effects of rebalancing events, the use of locks within a shard system can negatively impact system efficiency and performance. Perhaps worse still, unexpected failures within the shard system can cause a lock-holding process (which could be, for example, a client or a rebalancing process) to freeze up or otherwise quit functioning properly. Under such circumstances, the non-functional process may retain an exclusive lock on a particular data item until some timer expires, at which time the non-functional process may be terminated, and the locks it held forcibly released. Other processes, including clients and rebalancing processes, are consequently forced to wait for the timer's expiration before proceeding with their intended tasks relative to that particular data item. Especially if the operations to be performed relative to the particular data item are just one step within a strictly ordered sequence of operations to be performed relative to multiple separate data items, such forced waiting can cause the performance of the entire shard system to degrade noticeably. Dependencies imposed by orders in which operations often need to be performed can cause these kinds of complications to cascade.